

/**
 * Copyright 2007 Jason Horman, Pete Aykroyd
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.functor;

import java.util.*;

/**
 * Provides basic functional algorithms such as select, reject, apply as well as some boolean
 * algorithms that apply basic laws such as De Morgan's laws to simplify expressions to eliminate
 * nesting.
 */
public class Algorithms
{

    /** untested */
    public static <K, V> Map<K, V> map_reduce(Map<K, V> map,
                                              UnaryFunction<Pair<K, V>, Pair<K, V>> mapFunction,
                                              BinaryFunction<K, List<V>, Pair<K, V>> reduceFunction)
    {
        Map<K, List<V>> intermediate = new HashMap(map.size());
        for (Map.Entry<K, V> entry : map.entrySet())
        {
            Pair<K, V> result = mapFunction.evaluate(new Pair(entry.getKey(), entry.getValue()));

            if (!intermediate.containsKey(result.getFirst()))
                intermediate.put(result.getFirst(), new ArrayList());

            intermediate.get(result.getFirst()).add(result.getSecond());
        }

        Map<K, V> finalMap = new HashMap(intermediate.size());
        for (Map.Entry<K, List<V>> entry : intermediate.entrySet())
        {
            Pair<K, V> pair = reduceFunction.evaluate(entry.getKey(), entry.getValue());
            finalMap.put(pair.getFirst(), pair.getSecond());
        }

        return finalMap;
    }

    /**
     * Applies a function to each item in the list.
     */
    public static <ItemType, FunctionResult> List<FunctionResult>
    apply(Iterable<ItemType> iterable, String methodName)
    {
        return apply(iterable.iterator(), UnaryFunction.method(methodName));
    }

    /**
     * Applies a function to each item in the list.
     */
    public static <ItemType, FunctionResult> List<FunctionResult>
    apply(Iterable<ItemType> iterable, UnaryFunction<? super ItemType, FunctionResult> function)
    {
        return apply(iterable.iterator(), function);
    }

    /**
     * Applies a function to each item in the list.
     */
    public static <ItemType, FunctionResult> List<FunctionResult>
    apply(Iterator<ItemType> iterator, UnaryFunction<? super ItemType, FunctionResult> function)
    {
        List<FunctionResult> results = new ArrayList<FunctionResult>();
        while (iterator.hasNext())
        {
            results.add(function.evaluate(iterator.next()));
        }
        return results;
    }

    /**
     * Applies a function to each item in the list.
     */
    public static <ItemType, FunctionResult> List<FunctionResult>
    nullSafeApply(Iterable<ItemType> iterable, UnaryFunction<? super ItemType, FunctionResult> function)
    {
        return nullSafeApply(iterable.iterator(), function);
    }

    /**
     * Applies a function to each item in the list.
     */
    public static <ItemType, FunctionResult> List<FunctionResult>
    nullSafeApply(Iterator<ItemType> iterator, UnaryFunction<? super ItemType, FunctionResult> function)
    {
        List<FunctionResult> results = new ArrayList<FunctionResult>();
        while (iterator.hasNext())
        {
            FunctionResult result = function.evaluate(iterator.next());
            if (null != result)
                results.add(result);
        }
        return results;
    }

    /**
     * Filters a list.
     */
    public static <ItemType, TestType> List<ItemType> select(Iterable<ItemType> iterable, UnaryPredicate<TestType> predicate, UnaryFunction<ItemType, TestType> apply)
    {
        return select(iterable.iterator(), predicate, apply);
    }

    /**
     * Filters a list.
     */
    public static <ItemType> List<ItemType> select(Iterable<ItemType> iterable, UnaryPredicate<ItemType> predicate)
    {
        return select(iterable.iterator(), predicate, UnaryFunction.identity());
    }

    /**
     * Filters a list.
     */
    public static <ReturnType> List<ReturnType> select(Iterable iterable, Class instancesOfClazz)
    {
        return (List<ReturnType>) select(iterable.iterator(), UnaryPredicate.isInstance(instancesOfClazz), UnaryFunction.identity());
    }

    /**
     * Filters a list, applying the apply function to each before testing with the predicate.
     */
    public static <ItemType, TestType> List<ItemType> select(Iterator<ItemType> iterator, UnaryPredicate<TestType> predicate, UnaryFunction<ItemType, TestType> apply)
    {
        List<ItemType> results = new ArrayList<ItemType>();
        while (iterator.hasNext())
        {
            ItemType item = iterator.next();
            if (predicate.test(apply.evaluate(item)))
                results.add(item);
        }

        return results;
    }

    /**
     * Return the first item in the list of the specified class.
     */
    public static <ItemType> ItemType detect(Iterable iterable, Class instancesOfClazz)
    {
        return (ItemType) detect(iterable.iterator(), UnaryPredicate.isInstance(instancesOfClazz));
    }

    /**
     * Return the first item in the list that matches the predicate.
     */
    public static <ItemType> ItemType detect(Iterable<ItemType> iterable, UnaryPredicate<ItemType> predicate)
    {
        return detect(iterable.iterator(), predicate);
    }

    /**
     * Return the first item in the list that matches the predicate.
     */
    public static <ItemType> ItemType detect(Iterator<ItemType> iterator, UnaryPredicate<ItemType> predicate)
    {
        while (iterator.hasNext())
        {
            ItemType item = iterator.next();
            if (predicate.test(item))
                return item;
        }

        return null;
    }


    public static <ItemType> List<ItemType> reject(Iterable<ItemType> iterable, Class instanceOfClazz)
    {
        return reject(iterable.iterator(), UnaryPredicate.isInstance(instanceOfClazz));
    }

    /**
     * Returns a new list of just the items that DON'T match the predicate.
     */
    public static <ItemType> List<ItemType> reject(Iterable<ItemType> iterable, UnaryPredicate<ItemType> predicate)
    {
        return reject(iterable.iterator(), predicate);
    }

    /**
     * Returns a new list of just the items that DON'T match the predicate.
     */
    public static <ItemType> List<ItemType> reject(Iterator<ItemType> iterator, UnaryPredicate<ItemType> predicate)
    {
        List<ItemType> results = new ArrayList<ItemType>();
        while (iterator.hasNext())
        {
            ItemType item = iterator.next();
            if (!predicate.test(item))
                results.add(item);
        }

        return results;
    }

    public static <T, C extends Comparable> T max(Iterable<? extends T> iterable, UnaryFunction<T, C> getterFn)
    {
        return max(iterable.iterator(), getterFn);
    }

    public static <T, C extends Comparable> T max(Iterator<? extends T> iterator, UnaryFunction<T, C> getterFn)
    {
        T max = null;
        C maxValue = null;

        while (iterator.hasNext())
        {
            T item = iterator.next();
            if (max == null)
            {
                max = item;
                maxValue = getterFn.evaluate(item);
            }
            else if (getterFn.evaluate(item).compareTo(maxValue) > 0)
            {
                max = item;
                maxValue = getterFn.evaluate(item);
            }
        }

        return max;
    }

    public static <T, C extends Comparable> T min(Iterable<? extends T> iterable, UnaryFunction<T, C> getterFn)
    {
        return min(iterable.iterator(), getterFn);
    }

    public static <T, C extends Comparable> T min(Iterator<? extends T> iterator, UnaryFunction<T, C> getterFn)
    {
        T min = null;
        C minValue = null;

        while (iterator.hasNext())
        {
            T item = iterator.next();
            if (min == null)
            {
                min = item;
                minValue = getterFn.evaluate(item);
            }
            else if (getterFn.evaluate(item).compareTo(minValue) < 0)
            {
                min = item;
                minValue = getterFn.evaluate(item);
            }
        }

        return min;
    }

    /**
	 * Gets both the min and the max from a list only iterating the list once
	 *
	 * @return Pair of min and max in that order
	 */
	public static <T, C extends Comparable> Pair<T, T> minAndMax(Iterable<? extends T> iterable, UnaryFunction<T, C> getterFn) {
		return minAndMax(iterable.iterator(), getterFn);
	}

	/**
	 * Gets both the min and the max from a list only iterating the list once
	 *
	 * @return Pair of min and max in that order
	 */
	public static <T, C extends Comparable> Pair<T, T> minAndMax(Iterator<? extends T> iterator, UnaryFunction<T, C> getterFn) {
		T max = null;
		C maxValue = null;
		T min = null;
		C minValue = null;

		while (iterator.hasNext()) {
			T item = iterator.next();
			if (max == null) {
				max = item;
				maxValue = getterFn.evaluate(item);
			} else if (getterFn.evaluate(item).compareTo(maxValue) > 0) {
				max = item;
				maxValue = getterFn.evaluate(item);
			}
			if (min == null) {
				min = item;
				minValue = getterFn.evaluate(item);
			} else if (getterFn.evaluate(item).compareTo(minValue) < 0) {
				min = item;
				minValue = getterFn.evaluate(item);
			}
		}

		if (min == null)
			return null;

		return new Pair<T, T>(min, max);
	}

    /**
     * Return true if the iterator contains an item matching the predicate.
     */
    public static <ItemType> boolean contains(Iterable<ItemType> iterable, UnaryPredicate<ItemType> predicate)
    {
        return contains(iterable.iterator(), predicate);
    }

    /**
     * Return true if the iterator contains an item matching the predicate.
     */
    public static <ItemType> boolean contains(Iterator<ItemType> iterator, UnaryPredicate<ItemType> predicate)
    {
        while (iterator.hasNext())
        {
            ItemType item = iterator.next();
            if (predicate.test(item))
                return true;
        }

        return false;
    }

    public static <ItemType> UnaryPredicate<Iterable<ItemType>> contains(final UnaryPredicate<ItemType> predicate)
    {
        return new UnaryPredicate<Iterable<ItemType>>()
        {
            public boolean test(Iterable iterable) {
				return contains(iterable, predicate);
			}
		};
	}
}
